// @algorithm @lc id=38 lang=cpp 
// @title count-and-say


// #define print(...)
#define append(str, c) (str).push_back(c)
// @test(1)="1"
// @test(4)="1211"
class Solution {
public:
    string countAndSay(int n) {
        string dp = "1";
        for(int i=1; i<n; i++){
            string next;
            char ch = dp[0], n = '0';
            for(auto & c : dp){
                if(c == ch){
                    n++;
                    continue;
                }
                append(next, n);
                append(next, ch);
                ch = c;
                n = '1';
            }
            append(next, n);
            append(next, ch);
            dp = next;
            print("dp[", i, "]=", dp, "\n")
        }
        return dp;
    }
};